#ifndef _SELF_TEST
#include "config.h"
#include "sysy_lib.h"
#endif 

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <sys/types.h>

#include "buddy.h"

#define LEFT_LEAF(index) ((index) * 2 + 1)
#define RIGHT_LEAF(index) ((index) * 2 + 2)
#define PARENT(index) ( ((index) + 1) / 2 - 1)

#define IS_POWER_OF_2(x) (!((x)&((x)-1)))
#define MAX(a, b) ((a) > (b) ? (a) : (b))


//this will used for future, flexiable swith between ymalloc.
#ifdef _SELF_TEST
#define YASSERT
#endif
struct mem_alloc {
        uint8_t type;

        int (*init)(void *, size_t);
        int (*alloc)(void * handle, size_t);
        size_t (*free)(void * handle, size_t);
};

int buddy_init(void *buddy_addr, size_t page_num)
{
        struct buddy *buddy = (struct buddy *)buddy_addr;
        size_t i;
        size_t node_size;

        buddy->mpage_count = page_num;

        node_size = (size_t)page_num * 2;

        for (i = 0; i < page_num * 2 - 1; i++) {
                if (IS_POWER_OF_2(i + 1))
                        node_size /= 2;

                buddy->buddy_trees[i] = node_size;
        }

        return 0;
}

int buddy_alloc(void *buddy_addr, size_t size)
{
        struct buddy *buddy = (struct buddy *)buddy_addr;
        size_t index = 0;
        size_t node_size;
        size_t offset = 0;

        YASSERT(size > 0);

        if (!IS_POWER_OF_2(size))
                YASSERT(0);

        if (buddy->buddy_trees[index] < size) {
                //UNIMPLEMENTED(__DUMP__);
                return -1;
        }

        for (node_size = buddy->mpage_count; node_size != size; node_size /= 2) {
                if (buddy->buddy_trees[LEFT_LEAF(index)] >= size)
                        index = LEFT_LEAF(index);
                else
                        index = RIGHT_LEAF(index);
        }

        buddy->buddy_trees[index] = 0;
        offset = (index + 1) * node_size - buddy->mpage_count;

        while (index) {
                index = PARENT(index);
                buddy->buddy_trees[index] = MAX(buddy->buddy_trees[LEFT_LEAF(index)],
                                                buddy->buddy_trees[RIGHT_LEAF(index)]);
        }

        return offset;
}

size_t buddy_free(void *buddy_addr, size_t offset)
{
        struct buddy *buddy = (struct buddy *)buddy_addr;
        size_t node_size, index = 0;
        size_t left_longest, right_longest;

        YASSERT(buddy && offset < buddy->mpage_count);
        node_size = 1;
        index = offset + buddy->mpage_count - 1;

        for (; buddy->buddy_trees[index]; index = PARENT(index)) {
                node_size *= 2;
                if (index == 0)
                        return 0;
        }

        buddy->buddy_trees[index] = node_size;

        while (index) {
                index = PARENT(index);
                node_size *= 2;

                left_longest = buddy->buddy_trees[LEFT_LEAF(index)];
                right_longest = buddy->buddy_trees[RIGHT_LEAF(index)];

                if (left_longest + right_longest == node_size)
                        buddy->buddy_trees[index] = node_size;
                else
                        buddy->buddy_trees[index] = MAX(left_longest, right_longest);
        }

        return node_size;
}

struct mem_alloc mem_buddy = {
        .type = 0,      //todo, buddy type.
        .init = buddy_init,
        .alloc = buddy_alloc,
        .free = buddy_free
};

#ifdef _SELF_TEST
int main(int argc, char *argv[])
{
        int i,j;
        int total = 0;
        void *mem_ptr = malloc(4 * 1024 * 1024);

        mem_buddy.init(mem_ptr, 2048);

        for(j=2;j<32;j++) {
                for(i=0;;i++){
                        int ret = mem_buddy.alloc(mem_ptr, 1);
                        if(ret < 0)
                                break;

                        total ++;
                        if( i % j != 0){
                                mem_buddy.free(mem_ptr, ret);

                                total --;
                        }

                        printf("%d: %d, %d\r\n", j, i, total);
                }

                for(i=0;i<2048;i++) {
                        mem_buddy.free(mem_ptr, i);
                        total --;
                }
        }

        free(mem_ptr);
}
#endif
